/*
 * $Id: Morphing2D.java 3863 2010-10-26 02:53:32Z kschaefe $
 *
 * Copyright 2006 Sun Microsystems, Inc., 4150 Network Circle,
 * Santa Clara, California 95054, U.S.A. All rights reserved.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */
package org.jdesktop.swingx.geom;

import java.awt.Rectangle;
import java.awt.Shape;
import java.awt.geom.AffineTransform;
import java.awt.geom.FlatteningPathIterator;
import java.awt.geom.IllegalPathStateException;
import java.awt.geom.PathIterator;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;

/**
 * <p>
 * A morphing shape is a shape which geometry is constructed from two other
 * shapes: a start shape and an end shape.
 * </p>
 * <p>
 * The morphing property of a morphing shape defines the amount of
 * transformation applied to the start shape to turn it into the end shape.
 * </p>
 * <p>
 * Both shapes must have the same winding rule.
 * </p>
 *
 * @author Jim Graham
 * @author Romain Guy <romain.guy@mac.com> (Maintainer)
 */
public class Morphing2D implements Shape {
	private double morph;
	private Geometry startGeometry;
	private Geometry endGeometry;

	/**
	 * <p>
	 * Creates a new morphing shape. A morphing shape can be used to turn one
	 * shape into another one. The transformation can be controlled by the morph
	 * property.
	 * </p>
	 *
	 * @param startShape
	 *            the shape to morph from
	 * @param endShape
	 *            the shape to morph to
	 *
	 * @throws IllegalPathStateException
	 *             if the shapes do not have the same winding rule
	 * @see #getMorphing()
	 * @see #setMorphing(double)
	 */
	public Morphing2D(Shape startShape, Shape endShape) {
		startGeometry = new Geometry(startShape);
		endGeometry = new Geometry(endShape);
		if (startGeometry.getWindingRule() != endGeometry.getWindingRule()) {
			throw new IllegalPathStateException("shapes must use same " + "winding rule");
		}
		double tvals0[] = startGeometry.getTvals();
		double tvals1[] = endGeometry.getTvals();
		double masterTvals[] = mergeTvals(tvals0, tvals1);
		startGeometry.setTvals(masterTvals);
		endGeometry.setTvals(masterTvals);
	}

	/**
	 * <p>
	 * Returns the morphing value between the two shapes.
	 * </p>
	 *
	 * @return the morphing value between the two shapes
	 *
	 * @see #setMorphing(double)
	 */
	public double getMorphing() {
		return morph;
	}

	/**
	 * <p>
	 * Sets the morphing value between the two shapes. This value controls the
	 * transformation from the start shape to the end shape. A value of 0.0 is
	 * the start shape. A value of 1.0 is the end shape. A value of 0.5 is a new
	 * shape, morphed half way from the start shape to the end shape.
	 * </p>
	 * <p>
	 * The specified value should be between 0.0 and 1.0. If not, the value is
	 * clamped in the appropriate range.
	 * </p>
	 *
	 * @param morph
	 *            the morphing value between the two shapes
	 *
	 * @see #getMorphing()
	 */
	public void setMorphing(double morph) {
		if (morph > 1) {
			morph = 1;
		} else if (morph >= 0) {
			// morphing is finite, not NaN, and in range
		} else {
			// morph is < 0 or NaN
			morph = 0;
		}
		this.morph = morph;
	}

	private static double interp(double v0, double v1, double t) {
		return (v0 + ((v1 - v0) * t));
	}

	private static double[] mergeTvals(double tvals0[], double tvals1[]) {
		int i0 = 0;
		int i1 = 0;
		int numtvals = 0;
		while (i0 < tvals0.length && i1 < tvals1.length) {
			double t0 = tvals0[i0];
			double t1 = tvals1[i1];
			if (t0 <= t1) {
				i0++;
			}
			if (t1 <= t0) {
				i1++;
			}
			numtvals++;
		}
		double newtvals[] = new double[numtvals];
		i0 = 0;
		i1 = 0;
		numtvals = 0;
		while (i0 < tvals0.length && i1 < tvals1.length) {
			double t0 = tvals0[i0];
			double t1 = tvals1[i1];
			if (t0 <= t1) {
				newtvals[numtvals] = t0;
				i0++;
			}
			if (t1 <= t0) {
				newtvals[numtvals] = t1;
				i1++;
			}
			numtvals++;
		}
		return newtvals;
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public Rectangle getBounds() {
		return getBounds2D().getBounds();
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public Rectangle2D getBounds2D() {
		int n = startGeometry.getNumCoords();
		double xmin, ymin, xmax, ymax;
		xmin = xmax = interp(startGeometry.getCoord(0), endGeometry.getCoord(0), morph);
		ymin = ymax = interp(startGeometry.getCoord(1), endGeometry.getCoord(1), morph);
		for (int i = 2; i < n; i += 2) {
			double x = interp(startGeometry.getCoord(i), endGeometry.getCoord(i), morph);
			double y = interp(startGeometry.getCoord(i + 1), endGeometry.getCoord(i + 1), morph);
			if (xmin > x) {
				xmin = x;
			}
			if (ymin > y) {
				ymin = y;
			}
			if (xmax < x) {
				xmax = x;
			}
			if (ymax < y) {
				ymax = y;
			}
		}
		return new Rectangle2D.Double(xmin, ymin, xmax - xmin, ymax - ymin);
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean contains(double x, double y) {
		throw new InternalError("unimplemented");
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean contains(Point2D p) {
		return contains(p.getX(), p.getY());
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean intersects(double x, double y, double w, double h) {
		throw new InternalError("unimplemented");
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean intersects(Rectangle2D r) {
		return intersects(r.getX(), r.getY(), r.getWidth(), r.getHeight());
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean contains(double x, double y, double w, double h) {
		throw new InternalError("unimplemented");
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public boolean contains(Rectangle2D r) {
		return contains(r.getX(), r.getY(), r.getWidth(), r.getHeight());
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public PathIterator getPathIterator(AffineTransform at) {
		return new Iterator(at, startGeometry, endGeometry, morph);
	}

	/**
	 * {@inheritDoc}
	 */
	@Override
	public PathIterator getPathIterator(AffineTransform at, double flatness) {
		return new FlatteningPathIterator(getPathIterator(at), flatness);
	}

	private static class Geometry {
		static final double THIRD = (1.0 / 3.0);
		static final double MIN_LEN = 0.001;
		double bezierCoords[];
		int numCoords;
		int windingrule;
		double myTvals[];

		public Geometry(Shape s) {
			// Multiple of 6 plus 2 more for initial moveto
			bezierCoords = new double[20];
			PathIterator pi = s.getPathIterator(null);
			windingrule = pi.getWindingRule();
			if (pi.isDone()) {
				// We will have 1 segment and it will be all zeros
				// It will have 8 coordinates (2 for moveto, 6 for cubic)
				numCoords = 8;
			}
			double coords[] = new double[6];
			int type = pi.currentSegment(coords);
			pi.next();
			if (type != PathIterator.SEG_MOVETO) {
				throw new IllegalPathStateException("missing initial moveto");
			}
			double curx = bezierCoords[0] = coords[0];
			double cury = bezierCoords[1] = coords[1];
			double newx, newy;
			numCoords = 2;
			while (!pi.isDone()) {
				if (numCoords + 6 > bezierCoords.length) {
					// Keep array size to a multiple of 6 plus 2
					int newsize = (numCoords - 2) * 2 + 2;
					double newCoords[] = new double[newsize];
					System.arraycopy(bezierCoords, 0, newCoords, 0, numCoords);
					bezierCoords = newCoords;
				}
				switch (pi.currentSegment(coords)) {
					case PathIterator.SEG_MOVETO:
						throw new InternalError("Cannot handle multiple subpaths");
					case PathIterator.SEG_CLOSE:
						if (curx == bezierCoords[0] && cury == bezierCoords[1]) {
							break;
						}
						coords[0] = bezierCoords[0];
						coords[1] = bezierCoords[1];
						/* NO BREAK */
					case PathIterator.SEG_LINETO:
						newx = coords[0];
						newy = coords[1];
						// A third of the way from curxy to newxy:
						bezierCoords[numCoords++] = interp(curx, newx, THIRD);
						bezierCoords[numCoords++] = interp(cury, newy, THIRD);
						// A third of the way from newxy back to curxy:
						bezierCoords[numCoords++] = interp(newx, curx, THIRD);
						bezierCoords[numCoords++] = interp(newy, cury, THIRD);
						bezierCoords[numCoords++] = curx = newx;
						bezierCoords[numCoords++] = cury = newy;
						break;
					case PathIterator.SEG_QUADTO:
						double ctrlx = coords[0];
						double ctrly = coords[1];
						newx = coords[2];
						newy = coords[3];
						// A third of the way from ctrlxy back to curxy:
						bezierCoords[numCoords++] = interp(ctrlx, curx, THIRD);
						bezierCoords[numCoords++] = interp(ctrly, cury, THIRD);
						// A third of the way from ctrlxy to newxy:
						bezierCoords[numCoords++] = interp(ctrlx, newx, THIRD);
						bezierCoords[numCoords++] = interp(ctrly, newy, THIRD);
						bezierCoords[numCoords++] = curx = newx;
						bezierCoords[numCoords++] = cury = newy;
						break;
					case PathIterator.SEG_CUBICTO:
						bezierCoords[numCoords++] = coords[0];
						bezierCoords[numCoords++] = coords[1];
						bezierCoords[numCoords++] = coords[2];
						bezierCoords[numCoords++] = coords[3];
						bezierCoords[numCoords++] = curx = coords[4];
						bezierCoords[numCoords++] = cury = coords[5];
						break;
				}
				pi.next();
			}
			// Add closing segment if either:
			// - we only have initial moveto - expand it to an empty cubic
			// - or we are not back to the starting point
			if ((numCoords < 8) || curx != bezierCoords[0] || cury != bezierCoords[1]) {
				newx = bezierCoords[0];
				newy = bezierCoords[1];
				// A third of the way from curxy to newxy:
				bezierCoords[numCoords++] = interp(curx, newx, THIRD);
				bezierCoords[numCoords++] = interp(cury, newy, THIRD);
				// A third of the way from newxy back to curxy:
				bezierCoords[numCoords++] = interp(newx, curx, THIRD);
				bezierCoords[numCoords++] = interp(newy, cury, THIRD);
				bezierCoords[numCoords++] = newx;
				bezierCoords[numCoords++] = newy;
			}
			// Now find the segment endpoint with the smallest Y coordinate
			int minPt = 0;
			double minX = bezierCoords[0];
			double minY = bezierCoords[1];
			for (int ci = 6; ci < numCoords; ci += 6) {
				double x = bezierCoords[ci];
				double y = bezierCoords[ci + 1];
				if (y < minY || (y == minY && x < minX)) {
					minPt = ci;
					minX = x;
					minY = y;
				}
			}
			// If the smallest Y coordinate is not the first coordinate,
			// rotate the points so that it is...
			if (minPt > 0) {
				// Keep in mind that first 2 coords == last 2 coords
				double newCoords[] = new double[numCoords];
				// Copy all coordinates from minPt to the end of the
				// array to the beginning of the new array
				System.arraycopy(bezierCoords, minPt, newCoords, 0, numCoords - minPt);
				// Now we do not want to copy 0,1 as they are duplicates
				// of the last 2 coordinates which we just copied. So
				// we start the source copy at index 2, but we still
				// copy a full minPt coordinates which copies the two
				// coordinates that were at minPt to the last two elements
				// of the array, thus ensuring that thew new array starts
				// and ends with the same pair of coordinates...
				System.arraycopy(bezierCoords, 2, newCoords, numCoords - minPt, minPt);
				bezierCoords = newCoords;
			}
			/*
			 * Clockwise enforcement: - This technique is based on the formula
			 * for calculating the area of a Polygon. The standard formula is:
			 * Area(Poly) = 1/2 * sum(x[i]*y[i+1] - x[i+1]y[i]) - The returned
			 * area is negative if the polygon is "mostly clockwise" and
			 * positive if the polygon is "mostly counter-clockwise". - One
			 * failure mode of the Area calculation is if the Polygon is
			 * self-intersecting. This is due to the fact that the areas on each
			 * side of the self-intersection are bounded by segments which have
			 * opposite winding direction. Thus, those areas will have opposite
			 * signs on the accumulation of their area summations and end up
			 * canceling each other out partially. - This failure mode of the
			 * algorithm in determining the exact magnitude of the area is not
			 * actually a big problem for our needs here since we are only using
			 * the sign of the resulting area to figure out the overall winding
			 * direction of the path. If self-intersections cause different
			 * parts of the path to disagree as to the local winding direction,
			 * that is no matter as we just wait for the final answer to tell us
			 * which winding direction had greater representation. If the final
			 * result is zero then the path was equal parts clockwise and
			 * counter-clockwise and we do not care about which way we order it
			 * as either way will require half of the path to unwind and re-wind
			 * itself.
			 */
			double area = 0;
			// Note that first and last points are the same so we
			// do not need to process coords[0,1] against coords[n-2,n-1]
			curx = bezierCoords[0];
			cury = bezierCoords[1];
			for (int i = 2; i < numCoords; i += 2) {
				newx = bezierCoords[i];
				newy = bezierCoords[i + 1];
				area += curx * newy - newx * cury;
				curx = newx;
				cury = newy;
			}
			if (area < 0) {
				/*
				 * The area is negative so the shape was clockwise in a
				 * Euclidean sense. But, our screen coordinate systems have the
				 * origin in the upper left so they are flipped. Thus, this path
				 * "looks" ccw on the screen so we are flipping it to "look"
				 * clockwise. Note that the first and last points are the same
				 * so we do not need to swap them. (Not that it matters whether
				 * the paths end up cw or ccw in the end as long as all of them
				 * are the same, but above we called this section "Clockwise
				 * Enforcement", so we do not want to be liars. ;-)
				 */
				// Note that [0,1] do not need to be swapped with [n-2,n-1]
				// So first pair to swap is [2,3] and [n-4,n-3]
				int i = 2;
				int j = numCoords - 4;
				while (i < j) {
					curx = bezierCoords[i];
					cury = bezierCoords[i + 1];
					bezierCoords[i] = bezierCoords[j];
					bezierCoords[i + 1] = bezierCoords[j + 1];
					bezierCoords[j] = curx;
					bezierCoords[j + 1] = cury;
					i += 2;
					j -= 2;
				}
			}
		}

		public int getWindingRule() {
			return windingrule;
		}

		public int getNumCoords() {
			return numCoords;
		}

		public double getCoord(int i) {
			return bezierCoords[i];
		}

		public double[] getTvals() {
			if (myTvals != null) {
				return myTvals;
			}

			// assert(numCoords >= 8);
			// assert(((numCoords - 2) % 6) == 0);
			double tvals[] = new double[(numCoords - 2) / 6 + 1];

			// First calculate total "length" of path
			// Length of each segment is averaged between
			// the length between the endpoints (a lower bound for a cubic)
			// and the length of the control polygon (an upper bound)
			double segx = bezierCoords[0];
			double segy = bezierCoords[1];
			double tlen = 0;
			int ci = 2;
			int ti = 0;
			while (ci < numCoords) {
				double prevx, prevy, newx, newy;
				prevx = segx;
				prevy = segy;
				newx = bezierCoords[ci++];
				newy = bezierCoords[ci++];
				prevx -= newx;
				prevy -= newy;
				double len = Math.sqrt(prevx * prevx + prevy * prevy);
				prevx = newx;
				prevy = newy;
				newx = bezierCoords[ci++];
				newy = bezierCoords[ci++];
				prevx -= newx;
				prevy -= newy;
				len += Math.sqrt(prevx * prevx + prevy * prevy);
				prevx = newx;
				prevy = newy;
				newx = bezierCoords[ci++];
				newy = bezierCoords[ci++];
				prevx -= newx;
				prevy -= newy;
				len += Math.sqrt(prevx * prevx + prevy * prevy);
				// len is now the total length of the control polygon
				segx -= newx;
				segy -= newy;
				len += Math.sqrt(segx * segx + segy * segy);
				// len is now sum of linear length and control polygon length
				len /= 2;
				// len is now average of the two lengths

				/*
				 * If the result is zero length then we will have problems below
				 * trying to do the math and bookkeeping to split the segment or
				 * pair it against the segments in the other shape. Since these
				 * lengths are just estimates to map the segments of the two
				 * shapes onto corresponding segments of
				 * "approximately the same length", we will simply fudge the
				 * length of this segment to be at least a minimum value and it
				 * will simply grow from zero or near zero length to a
				 * non-trivial size as it morphs.
				 */
				if (len < MIN_LEN) {
					len = MIN_LEN;
				}
				tlen += len;
				tvals[ti++] = tlen;
				segx = newx;
				segy = newy;
			}

			// Now set tvals for each segment to its proportional
			// part of the length
			double prevt = tvals[0];
			tvals[0] = 0;
			for (ti = 1; ti < tvals.length - 1; ti++) {
				double nextt = tvals[ti];
				tvals[ti] = prevt / tlen;
				prevt = nextt;
			}
			tvals[ti] = 1;
			return (myTvals = tvals);
		}

		public void setTvals(double newTvals[]) {
			double oldCoords[] = bezierCoords;
			double newCoords[] = new double[2 + (newTvals.length - 1) * 6];
			double oldTvals[] = getTvals();
			int oldci = 0;
			double x0, xc0, xc1, x1;
			double y0, yc0, yc1, y1;
			x0 = xc0 = xc1 = x1 = oldCoords[oldci++];
			y0 = yc0 = yc1 = y1 = oldCoords[oldci++];
			int newci = 0;
			newCoords[newci++] = x0;
			newCoords[newci++] = y0;
			double t0 = 0;
			double t1 = 0;
			int oldti = 1;
			int newti = 1;
			while (newti < newTvals.length) {
				if (t0 >= t1) {
					x0 = x1;
					y0 = y1;
					xc0 = oldCoords[oldci++];
					yc0 = oldCoords[oldci++];
					xc1 = oldCoords[oldci++];
					yc1 = oldCoords[oldci++];
					x1 = oldCoords[oldci++];
					y1 = oldCoords[oldci++];
					t1 = oldTvals[oldti++];
				}
				double nt = newTvals[newti++];
				// assert(nt > t0);
				if (nt < t1) {
					// Make nt proportional to [t0 => t1] range
					double relt = (nt - t0) / (t1 - t0);
					newCoords[newci++] = x0 = interp(x0, xc0, relt);
					newCoords[newci++] = y0 = interp(y0, yc0, relt);
					xc0 = interp(xc0, xc1, relt);
					yc0 = interp(yc0, yc1, relt);
					xc1 = interp(xc1, x1, relt);
					yc1 = interp(yc1, y1, relt);
					newCoords[newci++] = x0 = interp(x0, xc0, relt);
					newCoords[newci++] = y0 = interp(y0, yc0, relt);
					xc0 = interp(xc0, xc1, relt);
					yc0 = interp(yc0, yc1, relt);
					newCoords[newci++] = x0 = interp(x0, xc0, relt);
					newCoords[newci++] = y0 = interp(y0, yc0, relt);
				} else {
					newCoords[newci++] = xc0;
					newCoords[newci++] = yc0;
					newCoords[newci++] = xc1;
					newCoords[newci++] = yc1;
					newCoords[newci++] = x1;
					newCoords[newci++] = y1;
				}
				t0 = nt;
			}
			bezierCoords = newCoords;
			numCoords = newCoords.length;
			myTvals = newTvals;
		}
	}

	private static class Iterator implements PathIterator {
		AffineTransform at;
		Geometry g0;
		Geometry g1;
		double t;
		int cindex;

		public Iterator(AffineTransform at, Geometry g0, Geometry g1, double t) {
			this.at = at;
			this.g0 = g0;
			this.g1 = g1;
			this.t = t;
		}

		/**
		 * {@inheritDoc}
		 */
		@Override
		public int getWindingRule() {
			return g0.getWindingRule();
		}

		/**
		 * {@inheritDoc}
		 */
		@Override
		public boolean isDone() {
			return (cindex > g0.getNumCoords());
		}

		/**
		 * {@inheritDoc}
		 */
		@Override
		public void next() {
			if (cindex == 0) {
				cindex = 2;
			} else {
				cindex += 6;
			}
		}

		double dcoords[];

		/**
		 * {@inheritDoc}
		 */
		@Override
		public int currentSegment(float[] coords) {
			if (dcoords == null) {
				dcoords = new double[6];
			}
			int type = currentSegment(dcoords);
			if (type != SEG_CLOSE) {
				coords[0] = (float) dcoords[0];
				coords[1] = (float) dcoords[1];
				if (type != SEG_MOVETO) {
					coords[2] = (float) dcoords[2];
					coords[3] = (float) dcoords[3];
					coords[4] = (float) dcoords[4];
					coords[5] = (float) dcoords[5];
				}
			}
			return type;
		}

		/**
		 * {@inheritDoc}
		 */
		@Override
		public int currentSegment(double[] coords) {
			int type;
			int n;
			if (cindex == 0) {
				type = SEG_MOVETO;
				n = 2;
			} else if (cindex >= g0.getNumCoords()) {
				type = SEG_CLOSE;
				n = 0;
			} else {
				type = SEG_CUBICTO;
				n = 6;
			}
			if (n > 0) {
				for (int i = 0; i < n; i++) {
					coords[i] = interp(g0.getCoord(cindex + i), g1.getCoord(cindex + i), t);
				}
				if (at != null) {
					at.transform(coords, 0, coords, 0, n / 2);
				}
			}
			return type;
		}
	}
}